package day_2022_9_to_12.Day;

import java.util.HashMap;
import java.util.Map;

/**
 * @author haomin
 * @date 2022/09/22 22:05
 **/
public class Day20_4_Num110_IsBalanced {
    class Solution {
        boolean flag= true;
        public boolean isBalanced(TreeNode root) {
            dfs(root);
            return flag;
        }
        private int dfs(TreeNode root){
            if(root == null) return 0;
            int left = dfs(root.left);
            int right = dfs(root.right);
            if(Math.abs(left-right) > 1) flag = false;
            return 1 + Math.max(left, right);
        }
    }
    class Solution2 {
        Map<TreeNode, Integer> map = new HashMap<>();
        boolean flag= true;
        public boolean isBalanced(TreeNode root) {
            dfs(root);
            return flag;
        }
        private int dfs(TreeNode root){
            if(root == null) return 0;
            int left = 0, right = 0;

            if(map.containsKey(root.left)){
                left = map.get(root.left);
            }else {
                left = dfs(root.left);
                map.put(root.left, left);
            }

            if(map.containsKey(root.right)){
                right = map.get(root.right);
            }else{
                right = dfs(root.right);
                map.put(root.right, right);
            }
            if(Math.abs(left-right) > 1) flag = false;
            return 1 + Math.max(left, right);
        }
    }
}